/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.medium._894;

import java.util.ArrayList;
import java.util.List;

/**
 * 返回包含 N 个结点的所有可能满二叉树的列表。 答案的每个元素都是一个可能树的根结点。
 * <p>
 * 答案中每个树的每个结点都必须有 node.val=0。
 * <p>
 * 你可以按任何顺序返回树的最终列表。
 * <p>
 *  
 * <p>
 * 示例：
 * <p>
 * 输入：7
 * 输出：[[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.medium._894
 * @ClassName: AllPossibleTree
 * @Author: linyaonan
 * @Date: 2020/1/16 17:13
 */
public class AllPossibleTree {

    public List<TreeNode> allPossibleFBT(int N) {
        List<TreeNode> result = new ArrayList<>();
        if (N % 2 == 0) {
            return result;
        }
        // 最终全部转化为1的节点
        if (N == 1) {
            TreeNode root = new TreeNode(0);
            result.add(root);
            return result;
        } else {
            // 所有可能的左右节点分布情况
            for (int i = 1; i < N; i += 2) {
                List<TreeNode> leftList = allPossibleFBT(i);
                List<TreeNode> rightList = allPossibleFBT(N - 1 - i);
                for (TreeNode leftNode : leftList) {
                    for (TreeNode rightNode : rightList) {
                        TreeNode treeNode = new TreeNode(0);
                        treeNode.left = leftNode;
                        treeNode.right = rightNode;
                        result.add(treeNode);
                    }
                }
            }
        }
        return result;
    }

}
